{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Evaluate the Bracket Pairs of a String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evaluate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #替换字符串中的括号内容"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串&nbsp;<code>s</code>&nbsp;，它包含一些括号对，每个括号中包含一个 <strong>非空</strong>&nbsp;的键。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>比方说，字符串&nbsp;<code>\"(name)is(age)yearsold\"</code>&nbsp;中，有&nbsp;<strong>两个</strong>&nbsp;括号对，分别包含键&nbsp;<code>\"name\"</code> 和&nbsp;<code>\"age\"</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你知道许多键对应的值，这些关系由二维字符串数组&nbsp;<code>knowledge</code>&nbsp;表示，其中&nbsp;<code>knowledge[i] = [key<sub>i</sub>, value<sub>i</sub>]</code>&nbsp;，表示键&nbsp;<code>key<sub>i</sub></code>&nbsp;对应的值为&nbsp;<code>value<sub>i</sub></code><sub>&nbsp;</sub>。</p>\n",
    "\n",
    "<p>你需要替换 <strong>所有</strong>&nbsp;的括号对。当你替换一个括号对，且它包含的键为&nbsp;<code>key<sub>i</sub></code>&nbsp;时，你需要：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>将&nbsp;<code>key<sub>i</sub></code>&nbsp;和括号用对应的值&nbsp;<code>value<sub>i</sub></code>&nbsp;替换。</li>\n",
    "\t<li>如果从 <code>knowledge</code>&nbsp;中无法得知某个键对应的值，你需要将&nbsp;<code>key<sub>i</sub></code>&nbsp;和括号用问号&nbsp;<code>\"?\"</code>&nbsp;替换（不需要引号）。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>knowledge</code>&nbsp;中每个键最多只会出现一次。<code>s</code>&nbsp;中不会有嵌套的括号。</p>\n",
    "\n",
    "<p>请你返回替换 <strong>所有</strong>&nbsp;括号对后的结果字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"(name)is(age)yearsold\", knowledge = [[\"name\",\"bob\"],[\"age\",\"two\"]]\n",
    "<b>输出：</b>\"bobistwoyearsold\"\n",
    "<strong>解释：</strong>\n",
    "键 \"name\" 对应的值为 \"bob\" ，所以将 \"(name)\" 替换为 \"bob\" 。\n",
    "键 \"age\" 对应的值为 \"two\" ，所以将 \"(age)\" 替换为 \"two\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"hi(name)\", knowledge = [[\"a\",\"b\"]]\n",
    "<b>输出：</b>\"hi?\"\n",
    "<b>解释：</b>由于不知道键 \"name\" 对应的值，所以用 \"?\" 替换 \"(name)\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>s = \"(a)(a)(a)aaa\", knowledge = [[\"a\",\"yes\"]]\n",
    "<b>输出：</b>\"yesyesyesaaa\"\n",
    "<b>解释：</b>相同的键在 s 中可能会出现多次。\n",
    "键 \"a\" 对应的值为 \"yes\" ，所以将所有的 \"(a)\" 替换为 \"yes\" 。\n",
    "注意，不在括号里的 \"a\" 不需要被替换。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= knowledge.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>knowledge[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= key<sub>i</sub>.length, value<sub>i</sub>.length &lt;= 10</code></li>\n",
    "\t<li><code>s</code>&nbsp;只包含小写英文字母和圆括号&nbsp;<code>'('</code>&nbsp;和&nbsp;<code>')'</code>&nbsp;。</li>\n",
    "\t<li><code>s</code>&nbsp;中每一个左圆括号&nbsp;<code>'('</code>&nbsp;都有对应的右圆括号&nbsp;<code>')'</code>&nbsp;。</li>\n",
    "\t<li><code>s</code>&nbsp;中每对括号内的键都不会为空。</li>\n",
    "\t<li><code>s</code>&nbsp;中不会有嵌套括号对。</li>\n",
    "\t<li><code>key<sub>i</sub></code>&nbsp;和&nbsp;<code>value<sub>i</sub></code>&nbsp;只包含小写英文字母。</li>\n",
    "\t<li><code>knowledge</code>&nbsp;中的&nbsp;<code>key<sub>i</sub></code>&nbsp;不会重复。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [evaluate-the-bracket-pairs-of-a-string](https://leetcode.cn/problems/evaluate-the-bracket-pairs-of-a-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [evaluate-the-bracket-pairs-of-a-string](https://leetcode.cn/problems/evaluate-the-bracket-pairs-of-a-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(name)is(age)yearsold\"\\n[[\"name\",\"bob\"],[\"age\",\"two\"]]', '\"hi(name)\"\\n[[\"a\",\"b\"]]', '\"(a)(a)(a)aaa\"\\n[[\"a\",\"yes\"]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if root.val == 2:\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif root.val == 3:\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if str(root.val) == '2':\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif str(root.val) == '3':\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if str(root.val) == '2':\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif str(root.val) == '3':\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val==1\n",
    "        if root.val==2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "                \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return (l or r) if root.val is 2 else (l and r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return bool(left or right) if root.val==2 else bool(left and right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:   \n",
    "        def dfs(node):\n",
    "            if node.left is None:\n",
    "                return True if  node.val == 1 else False\n",
    "            if node.val == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            match root.val:\n",
    "                case 0:\n",
    "                    return False\n",
    "                case 1:\n",
    "                    return True\n",
    "                case 2:\n",
    "                    return dfs(root.left) or dfs(root.right)\n",
    "                case 3:\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "        \n",
    "        return dfs(root)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2 :\n",
    "            return self.evaluateTree(root.right) or self.evaluateTree(root.left)\n",
    "        elif root.val == 3:\n",
    "            return  self.evaluateTree(root.right) and self.evaluateTree(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return \n",
    "        \n",
    "        if root.val == 2:\n",
    "            return bool(self.evaluateTree(root.left) or self.evaluateTree(root.right))\n",
    "        if root.val == 3:\n",
    "            return bool(self.evaluateTree(root.left) and self.evaluateTree(root.right))\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val==0 :\n",
    "            return False\n",
    "        if root.val==1:\n",
    "            return True\n",
    "        left_tree=self.evaluateTree(root.left)\n",
    "        right_tree=self.evaluateTree(root.right)\n",
    "        if root.val==2 or root.val==3:\n",
    "            if root.val==2:\n",
    "                return left_tree | right_tree\n",
    "            else:\n",
    "                return left_tree & right_tree\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 题目本身就是一个重复子问题\n",
    "# 我们可以求出root.left的bool值和root.right的bool值\n",
    "# 然后看root.val是or还是and 求最终结果返回即可\n",
    "# 递归出口就是叶子结点，判断root.left或者root.right是否为空即可\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val == 1\n",
    "        leftNums = self.evaluateTree(root.left)\n",
    "        rightNums = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return leftNums or rightNums\n",
    "        elif root.val == 3:\n",
    "            return leftNums and rightNums\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        match root.val:\n",
    "            case 0:\n",
    "                return False\n",
    "            case 1:\n",
    "                return True\n",
    "            case 2:\n",
    "                return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            case 3:\n",
    "                return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root):\n",
    "            if not root.left and not root.right:\n",
    "                return True if root.val==1 else False\n",
    "            return (dfs(root.left) and dfs(root.right)) if root.val == 3 else (dfs(root.left) or dfs(root.right))\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return left or right if root.val==2 else left and right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # '''\n",
    "        # 叶子节点:   0-False 1-True\n",
    "        # 非叶子节点: 2-Or    3-Add\n",
    "        # '''\n",
    "        # operators = {'2': 'or', '3': 'and'}\n",
    "        def traversal(root):\n",
    "            if not root: return None\n",
    "            if root.left and root.right and not root.left.left and not root.right.right:\n",
    "                if root.val == 2:\n",
    "                    root.val = root.left.val or root.right.val\n",
    "                elif root.val == 3:\n",
    "                    root.val = root.left.val and root.right.val\n",
    "                root.left = None\n",
    "                root.right = None\n",
    "            else:\n",
    "                traversal(root.left)\n",
    "                traversal(root.right)\n",
    "        while(root.left):\n",
    "            traversal(root)\n",
    "        return bool(root.val)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # if not root: return None\n",
    "        #     print(root.val)\n",
    "        #     # print(operators[str(root.val)])\n",
    "        #     if root.left and root.right and not root.left.left and not root.right.right:\n",
    "        #         print('qqqq')\n",
    "        #         print('root.val =',root.val)\n",
    "        #         if str(root.val) == '2':\n",
    "        #         # root.val = root.left.val operators[root.val] root.right.val\n",
    "        #             root.val = root.left.val or root.right.val\n",
    "        #             print('or root.val =', root.val)\n",
    "        #         elif str(root.val) == '3':\n",
    "        #             root.val = root.left.val and root.right.val\n",
    "        #             print('and root.val =', root.val)\n",
    "        #         root.left = None\n",
    "        #         root.right = None\n",
    "        #         print(str(root))\n",
    "        #         # pass\n",
    "        #     else:\n",
    "        #         print('pppp') \n",
    "        #         traversal(root.left)\n",
    "        #         traversal(root.right)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # # print(str(root))\n",
    "        # # traversal(root)\n",
    "        # while(root.left):\n",
    "        #     traversal(root)\n",
    "        # print(root)\n",
    "        # print(bool(root.val))\n",
    "        # return bool(root.val)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        #print(root)\n",
    "        if root.val == 2 :\n",
    "            if self.evaluateTree(root.left) :\n",
    "                return True\n",
    "            else :\n",
    "                return self.evaluateTree(root.right)\n",
    "        elif root.val == 3 :\n",
    "            if self.evaluateTree(root.left) :\n",
    "                return self.evaluateTree(root.right)\n",
    "            else :\n",
    "                return False\n",
    "        else :\n",
    "            return root.val == 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        if root.val == 3:\n",
    "            return left and right\n",
    "        return True if root.val==1 else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        \n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "\n",
    "        return (l or r) if root.val == 2 else (l and r) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left_val = self.evaluateTree(root.left)\n",
    "        right_val = self.evaluateTree(root.right)\n",
    "\n",
    "        if root.val == 2:\n",
    "            return left_val or right_val\n",
    "        elif root.val == 3:\n",
    "            return left_val and right_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return not not root.val\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return (l or r) if root.val is 2 else (l and r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val==3:return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        if root.val==2:return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return root.val==1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if not root.right and not root.left:\n",
    "            return  root.val==1\n",
    "        if root.val==2:\n",
    "            return  self.evaluateTree(root.left) or self.evaluateTree(root.right) \n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val in [0, 1]:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        if root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else: \n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def tf(root: Optional[TreeNode])-> bool:\n",
    "            if not root:\n",
    "                return False\n",
    "            if root.val == 0 :\n",
    "                return False\n",
    "            if root.val == 1 :\n",
    "                return True\n",
    "            tf(root.left)\n",
    "            tf(root.right)\n",
    "            if root:\n",
    "                if root.left:\n",
    "                    if root.val == 2:\n",
    "                        root.val = (root.left.val or root.right.val)\n",
    "                    elif root.val == 3:\n",
    "                        root.val = (root.left.val and root.right.val)\n",
    "                return root.val == 1\n",
    "        return tf(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 树不为空\n",
    "        if not root:\n",
    "            return bool(root.val)\n",
    "        if not root.left and not root.right:\n",
    "            return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        return bool(left or right) if root.val==2 else bool(left and right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dg(root):\n",
    "            if not root.left:\n",
    "                return bool(root.val)\n",
    "            if root.val == 2:\n",
    "                return dg(root.left) or dg(root.right)\n",
    "            if root.val == 3:\n",
    "                return dg(root.left) and dg(root.right)\n",
    "        return dg(root)\n",
    "            \n",
    "        #     dg(root.left)\n",
    "        #     if root.left:\n",
    "        #         root.left.val = 1\n",
    "        #     else:\n",
    "        #         root.left.val = 0\n",
    "        #     dg(root.right)\n",
    "        #     if root.right:\n",
    "        #         root.right.val = 1\n",
    "        #     else:\n",
    "        #         root.right.val = 0\n",
    "        #     if root.val == 2 and root.left.val == 0 and root.right.val == 0:\n",
    "        #         return False\n",
    "        #     if root.val == 2 and root.left.val == 0 or root.right.val ==0:\n",
    "        #         return True\n",
    "        #     if root.val == 3 and root.left.val == 1 and root.right.val == 1:\n",
    "        #         return True\n",
    "        #     if root.val == 3 and root.left.val == 0 or root.right.val == 0:\n",
    "        #         return False\n",
    "        # return dg(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2 :\n",
    "            return self.evaluateTree(root.right) or self.evaluateTree(root.left)\n",
    "        elif root.val == 3:\n",
    "            return  self.evaluateTree(root.right) and self.evaluateTree(root.left)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left: return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        self.evaluateTree(root.left)\n",
    "        self.evaluateTree(root.right)\n",
    "        if root.left and root.right:\n",
    "            if root.val == 2:\n",
    "                root.val = root.left.val | root.right.val\n",
    "            elif root.val == 3:\n",
    "                root.val = root.left.val & root.right.val\n",
    "        return bool(root.val)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.right is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        \n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "\n",
    "        return (l or r) if root.val == 2 else (l and r) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def getRes(root):\n",
    "            if root.val == 0:\n",
    "                return False\n",
    "            if root.val == 1:\n",
    "                return True\n",
    "            \n",
    "            l = getRes(root.left)\n",
    "            r = getRes(root.right)\n",
    "\n",
    "            if root.val == 2:\n",
    "                return l or r\n",
    "            if root.val == 3:\n",
    "                return l and r\n",
    "        \n",
    "        return getRes(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            v = node.val\n",
    "            if v < 2:\n",
    "                return bool(v)\n",
    "            elif v == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        elif root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        elif root.val == 0:\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left and not root.right:\n",
    "            return True if root.val == 1 else False\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        if root.val == 3:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "#递归算法\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root.left:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            #对象调用类成员函数时，要在函数名前加上self.或者类名.\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if (root.val < 2):\n",
    "            return root.val == 1\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None or root.right is None:\n",
    "            return bool(root.val)\n",
    "        left_flag = self.evaluateTree(root.left)\n",
    "        right_flag = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left_flag or right_flag\n",
    "        elif root.val == 3:\n",
    "            return left_flag and right_flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left == None:\n",
    "            return root.val == 1    #直接返回判断语句即可返回真假\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        #递归最重要一点：终止条件的返回值以及正常最后的返回值\n",
    "        #一般态可以当作返回的值判断\n",
    "        #同一root同一层级\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def find_real(root):\n",
    "            if root.left :\n",
    "                if root.val == 2 :\n",
    "                    return find_real(root.left) or find_real(root.right)\n",
    "                elif root.val == 3:\n",
    "                    return find_real(root.left) and find_real(root.right)\n",
    "            else :\n",
    "                return root.val\n",
    "        return True if find_real(root) else False "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node.left:\n",
    "                if node.val == 2:\n",
    "                    return dfs(node.left) or dfs(node.right)\n",
    "                elif node.val == 3:\n",
    "                    return dfs(node.left) and dfs(node.right)\n",
    "            return node.val == 1\n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return\n",
    "            left = dfs(node.left)\n",
    "            right = dfs(node.right)\n",
    "            if node.val == 2:\n",
    "                return left or right\n",
    "            if node.val == 3:\n",
    "                return left and right\n",
    "            if node.val == 0:\n",
    "                return False\n",
    "            if node.val == 1:\n",
    "                return True\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if root.left:\n",
    "            if root.val == 2:\n",
    "                return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "            else:\n",
    "                return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return root.val > 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.val == 0:\n",
    "            return False\n",
    "        elif root.val == 1:\n",
    "            return True\n",
    "        elif root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        elif root.val == 3:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "######注意factory={0:False,1:True,2: or,3:and}  or and等操作符只能作为操作符\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l = self.evaluateTree(root.left)\n",
    "        r = self.evaluateTree(root.right)\n",
    "        return l or r if root.val == 2 else l and r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if not node.left and not node.right:\n",
    "                    return node.val == 1\n",
    "                else:\n",
    "                    if node.val == 2:\n",
    "                        return dfs(node.left) or dfs(node.right)\n",
    "                    else:\n",
    "                        return dfs(node.left) and dfs(node.right)\n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root.val <= 1: return bool(root.val)\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        else:\n",
    "            return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if not root.left and not root.right:\n",
    "            return not not root.val\n",
    "        L = self.evaluateTree(root.left)\n",
    "        R = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return L or R\n",
    "        if root.val == 3:\n",
    "            return L and R\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        # 相当于后序\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            if root.left and root.right:  # 非叶子结点\n",
    "                if root.val == 2:\n",
    "                    return dfs(root.left) or dfs(root.right)\n",
    "                if root.val == 3:\n",
    "                    return dfs(root.left) and dfs(root.right)\n",
    "            if not root.left and not root.right:  # 叶子结点\n",
    "                return True if root.val==1 else False\n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(root) -> bool:\n",
    "            if not root.left and not root.right : return bool(root.val)\n",
    "            left , right = None,None\n",
    "            if root.left :\n",
    "                left = dfs(root.left)\n",
    "            if root.right :\n",
    "                right = dfs(root.right)\n",
    "            if root.val == 2 :\n",
    "                return left | right\n",
    "            return left & right\n",
    "        return dfs(root)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if not root:\n",
    "            return True\n",
    "        if not root.left and not root.right:\n",
    "            return not not root.val\n",
    "        L = self.evaluateTree(root.left)\n",
    "        R = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return L or R\n",
    "        if root.val == 3:\n",
    "            return L and R\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        l =self.evaluateTree(root.left)\n",
    "        r =self.evaluateTree(root.right)\n",
    "        return l or r if root.val==2 else l and r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def dfs(node):\n",
    "            if node.val < 2:\n",
    "                return node.val\n",
    "            elif node.val == 2:\n",
    "                return dfs(node.left) or dfs(node.right)\n",
    "            else:\n",
    "                return dfs(node.left) and dfs(node.right)\n",
    "                \n",
    "        return bool(dfs(root))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        def _find(n):\n",
    "            if not n.left:\n",
    "                return n.val\n",
    "            left = _find(n.left)\n",
    "            right = _find(n.right)\n",
    "            if n.val == 2:\n",
    "                return left or right\n",
    "            else:\n",
    "                return left and right\n",
    "            \n",
    "        return _find(root) == 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeNode:\n",
    "    def __init__(self, val=0, left=None, right=None):\n",
    "        self.val = val\n",
    "        self.left = left\n",
    "        self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return bool(root.val)\n",
    "        left=self.evaluateTree(root.left)\n",
    "        right=self.evaluateTree(root.right)\n",
    "        if root.val==2:\n",
    "            return left or right\n",
    "        else:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "\n",
    "        if root.val <= 1: return bool(root.val)\n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        if root.val == 2:\n",
    "            return left or right\n",
    "        else:\n",
    "            return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        \n",
    "        if not root.left and not root.right:\n",
    "            return root.val == 1\n",
    "        \n",
    "        left = self.evaluateTree(root.left)\n",
    "        right = self.evaluateTree(root.right)\n",
    "        val = root.val\n",
    "        if val == 2:\n",
    "            return left or right\n",
    "        return left and right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "        if root.left is None:\n",
    "            return root.val == 1\n",
    "        if root.val == 2:\n",
    "            return self.evaluateTree(root.left) or self.evaluateTree(root.right)\n",
    "        return self.evaluateTree(root.left) and self.evaluateTree(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def evaluateTree(self, root: Optional[TreeNode]) -> bool:\n",
    "      def dfs(root):\n",
    "        if root:\n",
    "          if not root.left and not root.right:\n",
    "            return root.val==1\n",
    "          else:\n",
    "            if root.val==2:\n",
    "              return dfs(root.left) or dfs(root.right) \n",
    "            else:\n",
    "              return dfs(root.left) and dfs(root.right) \n",
    "              \n",
    "        else:\n",
    "          return True\n",
    "      return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        return s.replace('(', '{').replace(')', '}').format_map(d := defaultdict(lambda: '?', knowledge))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        # 转换knowl为字典\n",
    "        paras = {i[0]: i[1] for i in knowledge}\n",
    "        stack = []\n",
    "        ret = ''\n",
    "        # 创建转换标识符\n",
    "        change = False\n",
    "        for i in s:\n",
    "            # 当左括号将标识符设置为True\n",
    "            if i == '(':\n",
    "                change = True\n",
    "            elif i == ')':\n",
    "                # 当遇到右括号，重置标识符与stack并开始判断knowledge\n",
    "                change = False\n",
    "                ret += paras.get(''.join(stack), '?')\n",
    "                stack = []\n",
    "            else:\n",
    "                # change为False追加字符串，为True时append栈等待获取key\n",
    "                if change:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    ret += i\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return re.sub('\\((\\w+)\\)', lambda m:d[m.group(1)], s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        return s.replace('(', '{').replace(')','}').format_map(defaultdict(lambda: '?', knowledge))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        knowledge = dict(knowledge)\n",
    "        return re.sub('\\([^)]+\\)', lambda m:knowledge.get(m.group(0)[1:-1], '?'), s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d={a:b for a,b in knowledge}\n",
    "        i,n=0,len(s)\n",
    "        ans=[]\n",
    "        while i<n:\n",
    "            if s[i]=='(':\n",
    "                j=s.find(')',i+1)\n",
    "                ans.append(d.get(s[i+1:j],'?'))\n",
    "                i=j\n",
    "            else:\n",
    "                ans.append(s[i])\n",
    "            i=i+1\n",
    "        return ''.join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        res, start = [], -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                start = i\n",
    "            elif c == ')':\n",
    "                res.append(d.get(s[start + 1:i], '?'))\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                res.append(c)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return re.sub('\\((\\w+)\\)', lambda m:d[m.group(1)], s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d, result, start = dict(knowledge), [], -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                start = i\n",
    "            elif c == ')':\n",
    "                result.append(d.get(s[start + 1: i], '?'))\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                result.append(c)\n",
    "        return \"\".join(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        n = len(s)\n",
    "        d = {}\n",
    "        for k, v in knowledge:\n",
    "            d[k] = v\n",
    "        i = 0\n",
    "        ans = ''\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                k = ''\n",
    "                j = i + 1\n",
    "                while j < n and s[j] != ')':\n",
    "                    k += s[j]\n",
    "                    j += 1\n",
    "                if s[i+1:j] in d:\n",
    "                    ans += d[s[i+1:j]]\n",
    "                else:\n",
    "                    ans += '?'\n",
    "                i = j + 1\n",
    "            else:\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        dic = {}\n",
    "        for item in knowledge:\n",
    "            dic[item[0]] = item[1]\n",
    "\n",
    "        a = re.findall(\"\\(([a-zA-Z]+)\\)\", s)\n",
    "        for key in a:\n",
    "            key1 = f\"({key})\"\n",
    "            s = s.replace(key1, dic.get(key, '?'))\n",
    "        s = s.replace(\"(\", \"\").replace(\")\", \"\")\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        key_map = {}\n",
    "        for t in knowledge:\n",
    "            key_map[t[0]]= t[1]\n",
    "        matches = re.findall('\\(.*?\\)',s)\n",
    "        for match in matches:\n",
    "            key = match.strip('(').strip(')')\n",
    "            if key in key_map:\n",
    "                s = s.replace(match,key_map[key])\n",
    "            else:\n",
    "                s = s.replace(match,'?')\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        # buffer_str = ''\n",
    "        res_lst = []\n",
    "        l_idx = 0\n",
    "        # r_idx = 0\n",
    "        for idx, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                l_idx = idx + 1\n",
    "            elif c == ')':\n",
    "                if s[l_idx:idx] in d:\n",
    "                    res_lst.append(d[s[l_idx:idx]])\n",
    "                else:\n",
    "                    res_lst.append('?')\n",
    "                l_idx = 0\n",
    "            else:\n",
    "                if l_idx == 0:\n",
    "                    res_lst.append(c)\n",
    "        return ''.join(res_lst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return s.replace('(', '{').replace(')', '}').format_map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return re.sub('\\([^)]+\\)', lambda m:d[m.group(0)[1:-1]], s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        stack = []\n",
    "        index = 0\n",
    "        key_value = {item[0]:item[1] for item in knowledge}\n",
    "\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                word = ''\n",
    "                while stack[-1] != '(':\n",
    "                    cur = stack.pop()\n",
    "                    word =  cur + word\n",
    "                stack.pop()\n",
    "                stack.append(key_value[word] if word in key_value else '?')\n",
    "        return ''.join(stack)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        mydict = defaultdict(str)\n",
    "        for k,v in knowledge:\n",
    "            mydict[k] = v\n",
    "        keys = re.findall('\\(([a-z]+)\\)',s)\n",
    "        print(keys)\n",
    "        for k in keys:\n",
    "            s = s.replace(f'({k})', mydict.get(k, '?'))\n",
    "        s = s.replace('(', '').replace(')', '')\n",
    "        # print(s)\n",
    "        return s\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        l = []\n",
    "        start = -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                start = i\n",
    "            elif c == ')':\n",
    "                l.append(d.get(s[start+1: i], '?'))\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                l.append(c)\n",
    "        return \"\".join(l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return s.replace('(', '{').replace(')', '}').format_map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        L = s.replace('(', ' (').replace(')', ') ').split()\n",
    "        d = dict(knowledge)\n",
    "        for idx, word in enumerate(L):\n",
    "            if word.startswith('('):\n",
    "                L[idx] = d.get(word.strip('()'), '?')\n",
    "        return ''.join(L)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        return re.sub(r\"\\((\\w+)\\)\", lambda matched: d.get(matched.groups(0)[0], \"?\"), s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "\n",
    "        n = len(knowledge)\n",
    "        k = 0\n",
    "        data = {}\n",
    "\n",
    "        def repl(m):\n",
    "            nonlocal k\n",
    "            key = m.group(1)\n",
    "            if key in data:\n",
    "                return data[key]\n",
    "            while k < n:\n",
    "                curKey = knowledge[k][0]\n",
    "                curValue = knowledge[k][1]\n",
    "                data[curKey] = curValue\n",
    "                k += 1\n",
    "                if curKey == key:\n",
    "                    return curValue\n",
    "            return \"?\"\n",
    "            \n",
    "\n",
    "        pattern = re.compile(r\"\\((.+?)\\)\")\n",
    "        return pattern.sub(repl, s)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        res, start = [], -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                start = i\n",
    "            elif c == ')':\n",
    "                res.append(d.get(s[start + 1:i], '?'))\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                res.append(c)\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        exc = dict(knowledge); ans = ''; flag = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                flag = 1    #switch\n",
    "                tem = ''\n",
    "                continue\n",
    "            if flag == 0:\n",
    "                ans += c\n",
    "            else:\n",
    "                if c == ')':\n",
    "                    if tem in exc.keys():\n",
    "                        ans += exc[tem]\n",
    "                    else: ans += '?'\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    tem += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = {}\n",
    "        keys = []\n",
    "        for l in knowledge:\n",
    "            d[l[0]] = l[1]\n",
    "        for i in range(len(s)-2):\n",
    "            if s[i] == '(':\n",
    "                for j in range(i, len(s)):\n",
    "                    if s[j] == ')':\n",
    "                        keys.append(s[i+1:j])\n",
    "                        i = j + 1\n",
    "                        break\n",
    "        for key in keys:\n",
    "            if key in d.keys():\n",
    "                s0 = d[key]\n",
    "            else:\n",
    "                s0 = '?'\n",
    "            s = s.replace(f'({key})', s0)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        key_value = dict()\n",
    "        for k, v in knowledge:\n",
    "            key_value[k] = v\n",
    "\n",
    "        s_len = len(s)\n",
    "        start_index = -1\n",
    "        r = ''\n",
    "        for i in range(s_len):\n",
    "            if s[i] == '(':\n",
    "                start_index = i\n",
    "            elif start_index != -1:\n",
    "                if s[i] == ')':\n",
    "                    key = s[start_index+1:i]\n",
    "                    value = '?'\n",
    "                    if key in key_value:\n",
    "                        value = key_value[key]\n",
    "                    r += value\n",
    "                    start_index = -1\n",
    "            else:\n",
    "                r += s[i]        \n",
    "\n",
    "        return r               \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = dict(knowledge)\n",
    "        ans, start = [], -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == '(':\n",
    "                start = i\n",
    "            elif c == ')':\n",
    "                ans.append(d.get(s[start + 1: i], '?'))\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                ans.append(c)\n",
    "        return \"\".join(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import re\n",
    "\n",
    "# class Solution:\n",
    "#     def evaluate(self, s: str, knowledge: list[list[str]]) -> str:\n",
    "#         s1 = s\n",
    "#         for dict1 in knowledge:\n",
    "#             key = \"(\" + dict1[0] + \")\"\n",
    "#             if key in s:\n",
    "#                 s1 = s1.replace(key, dict1[1])\n",
    "#         if '(' in s1:\n",
    "#             pattern = r'\\([^)]*\\)'\n",
    "#             s1 = re.sub(pattern, '?', s1)\n",
    "#         return s1\n",
    "\n",
    "# class Solution:\n",
    "#     def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "#         d = {a: b for a, b in knowledge}\n",
    "#         i, n = 0, len(s)\n",
    "#         ans = []\n",
    "#         while i < n:\n",
    "#             if s[i] == '(':\n",
    "#                 j = s.find(')', i + 1)\n",
    "#                 ans.append(d.get(s[i + 1: j], '?'))\n",
    "#                 i = j\n",
    "#             else:\n",
    "#                 ans.append(s[i])\n",
    "#             i += 1\n",
    "#         return ''.join(ans)\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        knowledge_table = {}\n",
    "        for key, val in knowledge:\n",
    "            knowledge_table[key] = val\n",
    "\n",
    "        res = \"\"\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            if s[i] == '(':\n",
    "                token = \"\"\n",
    "                while s[i]!=')':\n",
    "                    i += 1\n",
    "                    token += s[i]\n",
    "                i += 1\n",
    "                if token[:-1] not in knowledge_table:\n",
    "                    res += '?'\n",
    "                else :\n",
    "                    res += knowledge_table[token[:-1]]\n",
    "            else:\n",
    "                res += s[i]\n",
    "                i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        mp = defaultdict(lambda: '?')\n",
    "        for u, v in knowledge: mp[u] = v\n",
    "\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                j = i + 1\n",
    "                while i < n and s[i] != ')': i += 1\n",
    "                ans.append(mp[s[j : i]])\n",
    "            else:\n",
    "                ans.append(s[i])\n",
    "            i += 1\n",
    "        return ''.join(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        knowledge = dict(knowledge)\n",
    "        l, res, sub = 0, '', False\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == '(':\n",
    "                l = i\n",
    "                sub = True\n",
    "            elif s[i] == ')':\n",
    "                res += knowledge.get(s[l + 1: i], '?')\n",
    "                sub = False\n",
    "            elif not sub:\n",
    "                res += s[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return s.replace('(', '{').replace(')', '}').format_map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "        result = \"\"\n",
    "        index1 = 0   # 括号()之外各子串的开始索引\n",
    "        index2 = -1  # 与当前右括号匹配的，左括号所在的索引\n",
    "\n",
    "        m = len(knowledge)\n",
    "        k = 0        # 遍历 knowledge 的索引\n",
    "        data = {}    # 遍历 knowledge 时, 存储键值对, 无需从头从knowledge查找\n",
    "\n",
    "        # 遍历每个字符\n",
    "        for i in range(n):\n",
    "            c = s[i]\n",
    "            if c == \"(\":\n",
    "                # 遇到\"(\", 添加之前的字符串, 并记录此时的左括号索引\n",
    "                result += s[index1:i]\n",
    "                index1 = i\n",
    "                index2 = i\n",
    "            elif c == \")\" and index2 != -1:\n",
    "                # 遇到\")\", 从knowledge查找替换\n",
    "                key = s[index2 + 1:i]\n",
    "                if key in data:\n",
    "                    result += data[key]\n",
    "                else:\n",
    "                    flag = False\n",
    "                    while k < m:\n",
    "                        data[knowledge[k][0]] = knowledge[k][1]\n",
    "                        if knowledge[k][0] == key:\n",
    "                            flag = True\n",
    "                            result += knowledge[k][1]\n",
    "                            k += 1\n",
    "                            break\n",
    "                        k += 1\n",
    "                    if not flag:\n",
    "                        result += \"?\"\n",
    "                index1 = i + 1\n",
    "                index2 = -1\n",
    "\n",
    "        result += s[index1:n]\n",
    "        return result\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        ans,i = \"\",0\n",
    "        mydict = {key:value for key,value in knowledge}\n",
    "        while i < len(s):\n",
    "            if s[i] == \"(\":\n",
    "                key = \"\"\n",
    "                j = i + 1\n",
    "                while j < len(s) and s[j] != \")\":\n",
    "                    key += s[j]\n",
    "                    j += 1\n",
    "                if key in mydict.keys():\n",
    "                    ans += mydict[key]\n",
    "                else :\n",
    "                    ans += \"?\"\n",
    "                i = j+1\n",
    "            else :\n",
    "                ans += s[i]\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "\n",
    "        dic = {}\n",
    "        for k in knowledge:\n",
    "            dic[k[0]] = k[1]\n",
    "        start = -1\n",
    "        res = ''\n",
    "\n",
    "        for index, ch in enumerate(s):\n",
    "            if ch == '(':\n",
    "                start = index\n",
    "            elif ch == ')':\n",
    "                if s[start + 1: index] in dic:\n",
    "                    res = res + dic[s[start+1: index]]\n",
    "                else:\n",
    "                    res = res + '?'\n",
    "                start = -1\n",
    "            elif start < 0:\n",
    "                res += ch\n",
    "        \n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        keys = []\n",
    "        d = dict(knowledge)\n",
    "        for i in range(len(s)-2):\n",
    "            if s[i] == '(':\n",
    "                for j in range(i, len(s)):\n",
    "                    if s[j] == ')':\n",
    "                        keys.append(s[i+1:j])\n",
    "                        i = j + 1\n",
    "                        break\n",
    "        for key in keys:\n",
    "            if key in d.keys():\n",
    "                s0 = d[key]\n",
    "            else:\n",
    "                s0 = '?'\n",
    "            s = s.replace(f'({key})', s0)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        hashorder = dict()\n",
    "        for i in knowledge:\n",
    "            hashorder[i[0]] = i[1]\n",
    "        left = 0\n",
    "        while(left < len(s)):\n",
    "            if s[left]!='(':\n",
    "                left+=1\n",
    "            else:\n",
    "                right = left + 1\n",
    "                temp = ''\n",
    "                while(s[right] != ')'):\n",
    "                    temp = temp + s[right]\n",
    "                    right += 1\n",
    "                if temp in hashorder:\n",
    "                    s = s.replace(s[left:right+1], hashorder[temp])\n",
    "                    left = left + len(hashorder[temp])\n",
    "                else:\n",
    "                    s = s.replace(s[left:right+1] , '?')\n",
    "                    left = left + 1\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        stack = []\n",
    "        isopen = False\n",
    "        ans = \"\"\n",
    "        dic = {l[0]:l[1] for l in knowledge}\n",
    "        for i in s:\n",
    "            if i==\"(\":\n",
    "                isopen = True\n",
    "            elif i == \")\" :\n",
    "                isopen = False\n",
    "                s = \"\".join(stack)\n",
    "                stack = []\n",
    "                if s in dic:\n",
    "                    s = dic[s]\n",
    "                else:\n",
    "                    s = \"?\"\n",
    "                ans+=s\n",
    "            else:\n",
    "                if isopen:\n",
    "                    stack.append(i)\n",
    "                else:\n",
    "                    ans+=i\n",
    "                \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "\n",
    "        knowledge_d = {}\n",
    "       \n",
    "        for key,v in knowledge:\n",
    "            knowledge_d[key] = v\n",
    "        k1 = -1\n",
    "        k2 = -1\n",
    "        s_new  = ''\n",
    "\n",
    "        for i in range(len(s)):\n",
    "            \n",
    "            if s[i] == '(':\n",
    "                k1  = i\n",
    "    \n",
    "                \n",
    "            if s[i] == ')':\n",
    "                k2  = i \n",
    "                \n",
    "            #print(s_new,k1,k2)\n",
    "            if k1  == -1 and  k2 == -1:\n",
    "                s_new += s[i]\n",
    "\n",
    "            elif k1  >= 0 and  k2 >= 0:\n",
    "\n",
    "                #print(s_new,k1,k2)\n",
    "\n",
    "                s_new += knowledge_d.get(str(s[k1+1:k2]),'?')\n",
    "                k1 = -1\n",
    "                k2 = -1\n",
    "\n",
    "            else:\n",
    "                continue\n",
    "        return s_new"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        mapping = {}\n",
    "        for k,v in knowledge:\n",
    "            mapping[k] = v\n",
    "        n = len(s) \n",
    "        result = ''\n",
    "        i = 0\n",
    "        while(i < n):\n",
    "            if(s[i] =='('):\n",
    "                tmp = ''\n",
    "                i += 1\n",
    "                while(i<n and s[i]!=')'):\n",
    "                    tmp += s[i]\n",
    "                    i += 1\n",
    "                if(tmp in mapping):\n",
    "                    result += mapping[tmp]\n",
    "                else:\n",
    "                    result += '?'\n",
    "            else:\n",
    "                result += s[i]\n",
    "            i += 1\n",
    "        return result\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        hasmap = {x[0]: x[1] for x in knowledge}\n",
    "        res = \"\"\n",
    "        n = len(s)\n",
    "        i = 0 \n",
    "        while i < n:\n",
    "            if s[i] == \"(\":  \n",
    "                for j in range(i+1, n):\n",
    "                    if s[j] == \")\":\n",
    "                        res += hasmap[s[i+1:j]] if s[i+1:j] in hasmap else \"?\"\n",
    "                        i = j + 1\n",
    "                        break\n",
    "            else:\n",
    "                res += s[i]\n",
    "                i += 1 \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# import re\n",
    "\n",
    "# class Solution:\n",
    "#     def evaluate(self, s: str, knowledge: list[list[str]]) -> str:\n",
    "#         s1 = s\n",
    "#         for dict1 in knowledge:\n",
    "#             key = \"(\" + dict1[0] + \")\"\n",
    "#             if key in s:\n",
    "#                 s1 = s1.replace(key, dict1[1])\n",
    "#         if '(' in s1:\n",
    "#             pattern = r'\\([^)]*\\)'\n",
    "#             s1 = re.sub(pattern, '?', s1)\n",
    "#         return s1\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = {a: b for a, b in knowledge}\n",
    "        i, n = 0, len(s)\n",
    "        ans = []\n",
    "        while i < n:\n",
    "            if s[i] == '(':\n",
    "                j = s.find(')', i + 1)\n",
    "                ans.append(d.get(s[i + 1: j], '?'))\n",
    "                i = j\n",
    "            else:\n",
    "                ans.append(s[i])\n",
    "            i += 1\n",
    "        return ''.join(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        k_dic = {i[0]:i[1] for i in knowledge}\n",
    "        stack = []\n",
    "        kh_loc = 0\n",
    "        res = \"\"\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == \"(\":\n",
    "                res += s[kh_loc:i]\n",
    "                kh_loc = i\n",
    "            elif s[i] == \")\":\n",
    "                res += k_dic.get(s[kh_loc+1:i],\"?\")\n",
    "                kh_loc = i+1\n",
    "        res += s[kh_loc:] if s[-1] != \")\" else \"\"\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        k_dic = {i[0]:i[1] for i in knowledge}\n",
    "        stack = []\n",
    "        kh = False\n",
    "        for i in s:\n",
    "            if i!=\")\":\n",
    "                stack.append(i)\n",
    "            else:\n",
    "                local_res = \"\"\n",
    "                while True:\n",
    "                    v = stack.pop()\n",
    "                    if v == \"(\":\n",
    "                        break\n",
    "                    else:\n",
    "                        local_res = v + local_res\n",
    "                stack.append(k_dic.get(local_res,\"?\"))\n",
    "        return \"\".join(stack)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d=defaultdict(lambda:'?',knowledge)\n",
    "        return s.replace('(','{').replace(')','}').format_map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        dic = dict()\n",
    "        for x in knowledge:\n",
    "            dic[x[0]] = x[1]\n",
    "\n",
    "        l = 0\n",
    "        import copy\n",
    "        res = copy.deepcopy(s)\n",
    "        for y in range(len(s)):\n",
    "            if s[y] == \"(\":\n",
    "                l = y + 1\n",
    "                continue\n",
    "            if s[y] == \")\":\n",
    "                tmp = s[l:y]\n",
    "                if tmp in dic:\n",
    "                    res =res.replace(\"(\"+tmp+\")\", dic[tmp], 1)\n",
    "                else:\n",
    "                    res =res.replace(\"(\"+tmp+\")\", \"?\", 1)\n",
    "                l = 0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        know = {}\n",
    "        for key, val in knowledge:\n",
    "            know[key] = val\n",
    "\n",
    "        \n",
    "        res = []\n",
    "\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            while i < len(s) and s[i] != '(':\n",
    "                res.append(s[i])\n",
    "                i += 1\n",
    "            if i == len(s):\n",
    "                break\n",
    "            \n",
    "            start = i \n",
    "            i += 1\n",
    "\n",
    "            while i < len(s) and s[i] != ')':\n",
    "                i += 1\n",
    "            \n",
    "            end = i \n",
    "            key = s[start + 1:end]\n",
    "\n",
    "            if key in know:\n",
    "                res.append(know[key])\n",
    "            else:\n",
    "                res.append('?')\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return ''.join(res)            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        l1 = {}\n",
    "        p = -1\n",
    "        target = \"\"\n",
    "        x = \"\"\n",
    "        for i in range (len(knowledge)):\n",
    "            l1[knowledge[i][0]] = knowledge[i][1]\n",
    "        for i in range (len(s)):\n",
    "            if s[i] == \"(\":\n",
    "                p += 2\n",
    "            if s[i] == \")\":\n",
    "                p -= 1\n",
    "            if p == -1:\n",
    "                target += s[i]\n",
    "            elif p == 1:\n",
    "                if s[i] != \"(\":\n",
    "                    x += s[i]\n",
    "            else:\n",
    "                if x not in l1:\n",
    "                    target += \"?\"\n",
    "                else:\n",
    "                    target += l1[x]\n",
    "                p -= 1\n",
    "                x = \"\"\n",
    "        return target"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        d = defaultdict(lambda: '?', knowledge)\n",
    "        return s.replace('(', '{').replace(')', '}').format_map(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        cached = {}\n",
    "        for pair in knowledge:\n",
    "            cached[pair[0]] = pair[1]\n",
    "            pass\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] != '(':\n",
    "                i += 1\n",
    "                continue\n",
    "            j = i + 1\n",
    "            while j < len(s) and s[j] != ')':\n",
    "                j += 1\n",
    "            key = s[i + 1:j]\n",
    "            if key not in cached :\n",
    "                s = s[0:i] + '?' + s[j+1:len(s)]\n",
    "                pass\n",
    "            else:\n",
    "                s = s[0:i] + cached[key] + s[j+1:len(s)]\n",
    "                pass\n",
    "            i += 1\n",
    "            pass\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        hash_dict = {}\n",
    "        for kn in knowledge:\n",
    "            hash_dict[kn[0]] = kn[1]\n",
    "        isreplace = False\n",
    "        ret = \"\"\n",
    "        temp = \"\"\n",
    "        for alpha in s:\n",
    "            if alpha!=\")\" and isreplace:\n",
    "                temp += alpha\n",
    "            if alpha != \"(\" and not isreplace:\n",
    "                ret += alpha\n",
    "            if alpha == \"(\":\n",
    "                isreplace = True\n",
    "            if alpha==\")\":\n",
    "                if temp in hash_dict:\n",
    "                    ret += hash_dict[temp]\n",
    "                else:\n",
    "                    ret += \"?\"\n",
    "                isreplace = False\n",
    "                temp = \"\"\n",
    "        return ret\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        exc = {}\n",
    "        for key, v in knowledge:\n",
    "            exc[key] = v\n",
    "        ans = ''\n",
    "        flag = 0\n",
    "        for c in s:\n",
    "            if c == '(':\n",
    "                flag = 1    #switch\n",
    "                tem = ''\n",
    "                continue\n",
    "            if flag == 0:\n",
    "                ans += c\n",
    "            else:\n",
    "                if c == ')':\n",
    "                    if tem in exc.keys():\n",
    "                        ans += exc[tem]\n",
    "                    else: ans += '?'\n",
    "                    flag = 0\n",
    "                else:\n",
    "                    tem += c\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        ans = []\n",
    "        n = len(s)\n",
    "        idx = 0\n",
    "        map_ = {}\n",
    "        for know in knowledge:\n",
    "            map_[know[0]]= know[1]\n",
    "\n",
    "        while idx <n:\n",
    "            if s[idx] ==\"(\":\n",
    "                idx +=1\n",
    "                key = \"\"\n",
    "                while s[idx] !=\")\":\n",
    "                    key +=s[idx]\n",
    "                    idx +=1\n",
    "                idx +=1\n",
    "                print(key)\n",
    "                if key in map_.keys():\n",
    "                    ans.append(map_[key])\n",
    "                else:\n",
    "                    ans.append(\"?\")\n",
    "            else:\n",
    "                ans.append(s[idx])\n",
    "                idx+=1\n",
    "        return ''.join(ans)\n",
    "\n",
    "\n",
    "\n",
    "        # for ch in s:\n",
    "        #     if\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evaluate(self, s: str, knowledge: List[List[str]]) -> str:\n",
    "        mapping = dict()\n",
    "        for k, v in knowledge:\n",
    "            mapping[k] = v\n",
    "\n",
    "        def do(s):\n",
    "            if not s:\n",
    "                return s\n",
    "            start, end = -1, -1\n",
    "            for i, c in enumerate(s):\n",
    "                if c == \"(\":\n",
    "                    start = i\n",
    "                if c == \")\":\n",
    "                    end = i\n",
    "                    break\n",
    "            if start != -1 and end != -1:\n",
    "                result = s[:start] + mapping.get(s[start+1: end], \"?\") + do(s[end+1:])\n",
    "                return result\n",
    "            return s\n",
    "\n",
    "        def do2(s):\n",
    "            if not s:\n",
    "                return s\n",
    "            start, end = -1, -1\n",
    "            result = \"\"\n",
    "            for i, c in enumerate(s):\n",
    "                if c == \"(\":\n",
    "                    start = i\n",
    "                elif c == \")\":\n",
    "                    end = i\n",
    "                    result += mapping.get(s[start+1: end], \"?\")\n",
    "                    start = -1\n",
    "                elif start < 0:\n",
    "                    result += c\n",
    "            return result\n",
    "\n",
    "        return do2(s)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
